ARC111 A Simple Math 2
解法1
繰り返し二乗法の再帰的な式を変形する.
解法2
式を変形(しようと)してみる. 一旦切り捨てを除いて考えると,
$ 10^N = aM^2 + bM
と表せる. ここで
$ M^2
が出てくることから
$ 10^N
を
$ M^2
で割った余りを考えたらどうか, という発想につながる.
一般に, modAで管理しているときにBで割りたいときはmodABで考える というのが典型である
(解説放送より)m進数に変形することで導くこともできるらしい.
実装例(解法2):
https://atcoder.jp/contests/arc111/submissions/19300157